#ifndef TACORES_BREADTHFIRSTSEARCH_H
#define TACORES_BREADTHFIRSTSEARCH_H

using namespace std;

#include "Graph.h"
#include <vector>
#include <queue>
#include <limits>

// O(V + E)
class BreadthFirstSearch
{
public:
	BreadthFirstSearch(Graph& g)
		: g (g)
	{
	}

	void search(int s)
	{
		initialize();
		color[s] = Gray;
		dist[s] = 0;

		queue<int> que;
		que.push(s);
		while(que.empty() == false)
		{
			int u = que.front(); que.pop();
			VertexList::const_iterator end = g.end(u);
			for(VertexList::const_iterator it = g.begin(u); it != end; ++it)
			{
				int v = it->first;
				if(color[v] == White)
				{
					dist[v] = dist[u] + 1;
					pred[v] = u;
					color[v] = Gray;
					que.push(v);
				}
			}
			color[u] = Black;
		}
	}

	vector<int> getPredecessor() { return pred; }
	vector<int> getDistance() { return dist; }

private:
	void initialize()
	{
		int size = g.numVertices();
		pred.assign(size, -1);
		dist.assign(size, numeric_limits<int>::max());
		color.assign(size, White);
	}

	Graph& g;
	vector<int> pred;
	vector<int> dist;
	vector<vertexColor> color;
};
typedef BreadthFirstSearch BFS;

#endif

